#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int Element;

Element* generateOrderArray(int n) {
	Element* array = malloc(sizeof(Element) * n);
	if (array == NULL) {
		return NULL;
	}
	for (int i = 0; i < n; ++i) {
		array[i] = i;
	}
	return array;
}
// 二分查找
/* 数组空间有序，在闭区间搜索[0...n-1]
 * 确定left和rightd的区间，定位mid值，根据mid值来确定是左边还是再右边
 */
int binarySearchV1(const Element *arr, int n, Element target) {
	int left = 0;
	int right = n - 1;

	while (left <= right) {
		// int mid = (left + right) / 2;
		int mid = left + (right - left) / 2;
		if (arr[mid] == target) {
			return target;
		} else if (arr[mid] < target) {
			left = mid + 1;
		} else {
			right = mid -1;
		}
	}
	return -1;
}

/* [0...n)*/
int binarySearchV2(const Element *arr, int n, Element target) {
	int left = 0;
	int right = n;
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] == target) {
			return target;
		} else if (arr[mid] < target) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return -1;
}

// 普通查找
Element normalSearch(const Element *arr, int n, Element target) {
	for (int i = 0; i < n; ++i) {
		if (arr[i] == target) {
			return target;
		}
	}
	return -1;
}



int main() {
	int n = 100000;
	Element* array = generateOrderArray(n);
	if (array == NULL) {
		return -1;
	}
	clock_t start = clock();
	for (int i = 0; i < n; ++i) {
		if (i != binarySearchV2(array, n, i)) {
			printf("Not find!\n");
		}
	}
	clock_t end = clock();
	printf("Time 1 cost: %f s\n", (double)(end - start) / CLOCKS_PER_SEC);
	start = clock();
	for (int i = 0; i < n; ++i) {
		if (i != normalSearch(array, n, i)) {
			printf("Not Find!\n");
		}
	}
	end = clock();
	printf("Time 2 cost: %f s\n", (double)(end - start) / CLOCKS_PER_SEC);

	free(array);
	return 0;
}
